'lintcode 两个链表的交叉'

Posted on | In

描述

请写一个程序，找到两个单链表最开始的交叉节点。

如果两个链表没有交叉，返回null。
在返回结果后，两个链表仍须保持原有的结构。
可假定整个链表结构中没有循环。

样例

下列两个链表：

A:                   a1 → a2
                                   ↘
                                    c1 → c2 → c3
                             ↗
B: b1 → b2 → b3
在节点 c1 开始交叉。

挑战

需满足 O(n) 时间复杂度，且仅用 O(1) 内存。

思路

先分别遍历一次链表，得到2个链表的长度，然后差值delt就是交叉之前的差值，只要让长一点的先走delt，最后一起走，相遇时就是入口

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
/**
 * Definition of singly-linked-list:
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *        this->val = val;
 *        this->next = NULL;
 *     }
 * }
 */

class Solution {
public:
    /**
     * @param headA: the first list
     * @param headB: the second list
     * @return: a ListNode
     */
    ListNode * getIntersectionNode(ListNode * headA, ListNode * headB) {
        // write your code here
        if (!headA || !headB) return NULL;
        ListNode *pa = headA, *pb = headB;
        int na = 0, nb = 0;
        while (pa) {
            pa = pa->next;
            na++;
        }
        while (pb) {
            pb = pb->next;
            nb++;
        }
        int delt = abs(na-nb);
        if (na < nb) {
            pa = headA;
            pb = headB;
            while (delt > 0) {
                pb = pb->next;
                delt--;
            }
            while (pa != pb) {
                pa = pa->next;
                pb = pb->next;
            }
            return pa;
        }
        else {
            pa = headA;
            pb = headB;
            while (delt > 0) {
                pa = pa->next;
                delt--;
            }
            while (pa != pb) {
                pa = pa->next;
                pb = pb->next;
            }
            return pa;
        }
    }
};
-------------end of filethanks for reading-------------